home *** CD-ROM | disk | FTP | other *** search
/ Giga Games 1 / Giga Games.iso / net / go / info / maxgro.ups < prev    next >
Encoding:
Text File  |  1993-06-20  |  14.3 KB  |  365 lines
  1.        How many live groups can there be on a go board?
  2.  
  3. [Note:  I changed all black stones to # for consistency.  --editor]
  4.  
  5. Subject: Number of live groups.
  6. From: wft@math.canterbury.ac.nz (Bill Taylor)
  7.  
  8. Yijun Ding asks what is the maximum possible number of groups
  9. in a game.
  10.  
  11. Yes; I know he was asking for a practical maximum, for computer
  12. programming purposes, rather than a theoretical one; but I choose
  13. to interpret it the latter way.   After all, it's clear that there's
  14. way too many computer scientists on rec.games.go and not nearly
  15. enough mathematicians    ;-)   .
  16.  
  17. Anyway, the question, the maximum possible number of groups on the
  18. board, has two interpretations (at least).
  19.  
  20. 1: Maximum number independently alive.
  21. 2: Maximum number alive in seki (or similar).
  22.  
  23. Both of these are difficult to define unambiguously, without 134
  24. densely printed pages of Japanese-style-rule bookishness. However
  25. we'll take for granted, (temporarily), that we all know what we mean.
  26.  
  27. It's already been mentioned that things like     O . O . . .
  28. might be considered as either one or two         . O O . .
  29. groups, but I'll assume that it's clearly        O O O .
  30. one, in the spirit of the regular rules.         . . . .
  31.  
  32. Whereas something like this (on a 4x4 board),
  33. would have to be counted as four groups,          . # O O
  34. two black and two white. The separate halves      # . O #
  35. of the black groups are `connected' by a          O O . #
  36. uni-colored eye; this doesn't hold for the        # # # .
  37. two white bits.
  38.  
  39. Anyway, none of this appears to be relevant for the answers to
  40. questions 1 and 2 above; on a 19x19 board at least.
  41.  
  42. I get answers of 28, and 60, respectively.
  43. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  44. As always, I would be delighted to see anyone write in with improvements.
  45.  
  46. Here are my solutions.
  47.  
  48.  1:      . O # . # O . O # . # O . O # . # O .
  49.          O O # # # O O O # # # O O O # # # O O
  50.          . O # . # O . O # . # O . O # . # O .
  51.          O O # # # O O O # # # O O O # # # O O
  52.          # # O O O # # # O O O # # # O O O # #
  53.          . # O . O # . # O . O # . # O . O # .
  54.          # # O O O # # # O O O # # # O O O # #
  55.          . # O . O # . # O . O # . # O . O # .
  56.          # # O O O # # # O O O # # # O O O # #
  57.          O O # # # O O O # # # O O O # # # O O
  58.          . O # . # O . O # . # O . O # . # O .
  59.          O O # # # O O O # # # O O O # # # O O
  60.          . O # . # O . O # . # O . O # . # O .
  61.          O O # # # O O O # # # O O O # # # O O
  62.          # # O O O # # # O O O # # # O O O # #
  63.          . # O . O # . # O . O # . # O . O # .
  64.          # # O O O # # # O O O # # # O O O # #
  65.          . # O . O # . # O . O # . # O . O # .
  66.          . # O . O # . # O . O # . # O . O # .    28 groups fully alive.
  67.  
  68.  
  69.   2:     # . O # . O # . O # . O # . O # . O O
  70.          # . O # . O # . O # . O # . O # . O O
  71.          # # O # # O # # O # # O # # O # # O O
  72.          O O # O O # O O # O O # O O # O O # #
  73.          O . # O . # O . # O . # O . # O . # #
  74.          O . # O . # O . # O . # O . # O . # #
  75.          O O # O O # O O # O O # O O # O O # #
  76.          # # O # # O # # O # # O # # O # # O O
  77.          # . O # . O # . O # . O # . O # . O O
  78.          # . O # . O # . O # . O # . O # . O O
  79.          # # O # # O # # O # # O # # O # # O O
  80.          O O # O O # O O # O O # O O # O O # #
  81.          O . # O . # O . # O . # O . # O . # #
  82.          O . # O . # O . # O . # O . # O . # #
  83.          O O # O O # O O # O O # O O # O O # #
  84.          # # O # # O # # O # # O # # O # # O O
  85.          # . O # . O # . O # . O # . O # . O O
  86.          # . O # . O # . O # . O # . O # . O O
  87.          # # O # # O # # O # # O # # O # # O O   60 groups alive in seki.
  88.  
  89.  
  90.  
  91. From: smith@pell.anu.edu.au (Michael Smith)
  92.  
  93. I didn't have time to fine tune this -- It might be possible to get an extra
  94. group one the edge somewhere.
  95.  
  96. Simply based on regular pattern in capital stones :-) which are a more
  97. efficient way of covering the board than the way you chose:
  98.  
  99. Instead of 15 intersections for the groups in the centre, I only use 12.
  100.  
  101. However I only get one extra fully alive group for a total of 29:
  102.  
  103.  # # # # O O . O # # # # # # # # o o .
  104.  # # . # O . O O # # O O # # . # o . o
  105.  # . # # O O # # O O . O # . # # o o o
  106.  # # O O # # . # O . O O # # O O # # #
  107.  O O . O # . # # O O # # O O . O # # .
  108.  O . O O # # O O # # . # O . O O # . #
  109.  O O # # O O . O # . # # O O # # o # #
  110.  # # . # O . O O # # O O # # . # o o o
  111.  # . # # O O # # O O . O # . # # o # #
  112.  # # O O # # . # O . O O # # O O o # .
  113.  O O . O # . # # O O # # O O . O # . #
  114.  O . O O # # O O # # . # O . O O # # #
  115.  O O # # O O . O # . # # O O # # o o o
  116.  # # . # O . O O # # O O # # . # o . o
  117.  # . # # O O # # O O . O # . # # o o .
  118.  # # O O # # . # O . O O # # O O # o o
  119.  O O . O # . # # O O # # O O . O # # #
  120.  O . O O # # o o # # . # O . O O # # .
  121.  O O o o o o o o # . # # O O # # # . #
  122.  
  123.  
  124. But I think with a bit more thought I can fine tune this.
  125.  
  126. Next question is how can you PROVE that a certain number is the maximum -
  127. apart from trying every combination of alive stones on a board and counting.
  128.  
  129.  
  130. From: wft@math.canterbury.ac.nz (Bill Taylor)
  131.  
  132. Following up my own post, I'm able to improve one of my records for
  133. the maximum number of live groups on a go board.
  134.  
  135. The formation is....
  136.  
  137.      . # . O . # . O . # . O . # . O . # .
  138.      # # O O # # O O # # O O # # O O # # #
  139.      O O # # O O # # O O # # O O # # O O O
  140.      . O . # . O . # . O . # . O . # . O .
  141.      O O # # O O # # O O # # O O # # O O O
  142.      # # O O # # O O # # O O # # O O # # #
  143.      . # . O . # . O . # . O . # . O . # .
  144.      # # O O # # O O # # O O # # O O # # #
  145.      O O # # O O # # O O # # O O # # O O O
  146.      . O . # . O . # . O . # . O . # . O .
  147.      O O # # O O # # O O # # O O # # O O O
  148.      # # O O # # O O # # O O # # O O # # #
  149.      . # . O . # . O . # . O . # . O . # .
  150.      # # O O # # O O # # O O # # O O # # #
  151.      O O # # O O # # O O # # O O # # O O O
  152.      . O . # . O . # . O . # . O . # . O .
  153.      O O # # O O # # O O # # O O # # O O O
  154.      # # O O # # O O # # O O # # O O # # #
  155.      . # . O . # . O . # . O . # . O . # .
  156.  
  157. which has 63 live groups alive in seki.
  158.  
  159.  
  160. From: wolfe@vina.Berkeley.EDU (David Wolfe)
  161.  
  162. I've worked on the problem of fitting the most live "strings" on a
  163. board, where a string is a connected group of stones, and a live
  164. string includes life in seki.
  165.  
  166. My understanding of Niek van Diespen's posting is that the solution is
  167. somewhere in the 130's:
  168. > Sometimes I'm simply too fast: Ger Hungerink also addressed the version
  169. > with seki's. I did not put too much time in that, but the maximum is
  170. > somewhere in the 130's, if I remember correctly. My last posting of
  171. > course only addressed the "Independently alive" case.
  172.  
  173. I have a solution which has only 108 strings, and solves Bill Taylors
  174. original posting as well with 104 groups:
  175.  
  176. . O # # O # . # O # O O O O O # # . #
  177. O . # # O # # . O # O . O . # O # # .
  178. # # . O O # # O . # # O O # . O O # #
  179. # # O . # O O # # . O # # O O . # O O
  180. O O O # . O O # # O . # # O O # . O O
  181. # # # O O . # O O # # . O # # O O . #
  182. . # # O O # . O O # # O . # # O O # .
  183. # . O # # O O . # O O # # . O # # O O
  184. O O . # # O O # . O O # # O . # # O O
  185. # # # . O # # O O . # O O # # . O # .
  186. O O # O . # # O O # . O O # # O O . #
  187. O . O # # . O # # O O . # O O # . O O
  188. O O O # # O . # # O O # . O O # # # #
  189. O . # O O # # . O # # O O . # O O # .
  190. O # . O O # # O . # # O O # . O O # #
  191. # O O . # O O # # . O # # O O . # O O
  192. # # O # . O O # # O O . # O O # . O O
  193. . # # O O . # O O # . O # # # O O . #
  194. # . # O O # . O O . # O # . # O O # .
  195.  
  196. David Wolfe
  197. wolfe@melody.berkeley.edu
  198.  
  199.  
  200. From: herbison@manage.enet.dec.com (B.J.)
  201.  
  202. >I have a solution which has only 108 strings, and solves Bill Taylors
  203. >original posting as well with 104 groups:
  204. >
  205. |. O # # O # . # O # O O O O O # # . #
  206. |O . # # O # # . O # O . O . # O # # .
  207. |# # . O O # # O . # # O O # . O O # #
  208. |# # O . # O O # # . O # # O O . # O O
  209. |O O O # . O O # # O . # # O O # . O O
  210. |# # # O O . # O O # # . O # # O O . #
  211. |. # # O O # . O O # # O . # # O O # .
  212. |# . O # # O O . # O O # # . O # # O O
  213. |O O . # # O O # . O O # # O . # # O O
  214. |# # # . O # # O O . # O O # # . ! # .
  215. |O O # O . # # O O # . O O # # ! ! . #
  216. |O . O # # . O # # O O . # O O # . O O
  217. |O O O # # O . # # O O # . O O # # # #
  218. |O . # O O # # . O # # O O . # O O # .
  219. |O # . O O # # O . # # O O # . O O # #
  220. |# O O . # O O # # . ! # # O O . # O O
  221. |# # O # . O O # # ! ! . # O O # . O O
  222. |. # # O O . # O O # . O # # # O O . #
  223. |# . # O O # . O O . # O # . # O O # .
  224.  
  225. There are two O groups in this diagram with three liberties.
  226. (I replaced the Os with !s to make them stand out.)  From
  227. this configuration, O can capture most of the board.
  228.  
  229.  
  230. From: wft@math.canterbury.ac.nz (Bill Taylor)
  231.  
  232. I've been plugging away at this business of maximum number of LIVE groups
  233. possible on the board.  (Of course without the "live" restriction, the
  234. checkerboard patterns that have been posted will easily win).
  235.  
  236. I'm now convinced that the best    . # # O O . # O # # .
  237. patterns will have a basic shape   # . O # O # . O O # O   average group
  238. like that shown here, ---------->  # O . # # O O . # O #     size: 
  239. which must be the max possible     O # # . O # O # . O O 
  240. density of live groups in an       O O # O . # # O O . #   2.5 intersections
  241. infinite board. (These groups are  . # O # # . O # O # .       per group.
  242. only alive in seki, of course.)    # . O O # O . # # O O
  243.  
  244. This density is noticably better than any other solutions seen on the net.
  245.  
  246. It's a bit tricky fitting in stuff round the edges of a finite board, though.
  247. In view of the messy nature of my solution, and the alleged Dutch publication
  248. of a 130-odd group formation, I'm far from sure this is best possible. It
  249. must be close though.
  250.  
  251. So here's my solution;128 groups (counting orthogonal connections only)
  252.                       114 groups (counting 2 bits joined by an eye as the same)
  253.  
  254. . # O O # . O . O O . # O O # . # O #
  255. # . O O # # # O O O # . O O # # . O #
  256. O O . # O # . # # # O O . # O # O . #
  257. O O # . O O # # . O # O # . O O # # .
  258. # # O O . # O # O . # # O O . # O # # 
  259. . # # O # . O O # # . O # O # . O O #
  260. O # . # O O . # O # O . # # O O . # O
  261. . O # # # O # . O O # # . O # O # . O
  262. O O # . O # O O . # O # O . # # O O .
  263. O O # O . # # O # . O O # # . O # O O
  264. . # O # # . O # O O . # O # O . # # O
  265. # . O O # O . # # O # . O O # # . O #
  266. O O . # O # # . O # O O . # O # O . #
  267. O O # . O O # O . # # O # . O O # # .
  268. # # O O . # O # # . O # O O . # O # #
  269. . # # O # . O O # O . # # O # . O O #
  270. # . O # O O . # O # # . O # O O . # O
  271. O O . # # O # . O O # O . # # O # . O 
  272. # # # . # # O O . O O # # . # # O O .
  273.  
  274. Interestingly, (in Chinese counting), the result of the game is an
  275. eact tie !   ( 151 points each, with 59 neutral).
  276.  
  277. From: maiorana%idacrd.uucp@princeton.edu (James Maiorana)
  278.  
  279.      This article is in reponse to wft@math.canterbury.ac.nz (Bill Taylor)'s
  280. message dated 21 May 92 04:19:15 GMT.  He writes
  281.  
  282. > I'm now convinced that the best    . # # O O . # O # # .
  283. > patterns will have a basic shape   # . O # O # . O O # O   average group
  284. > like that shown here, ---------->  # O . # # O O . # O #     size: 
  285. > which must be the max possible     O # # . O # O # . O O 
  286. > density of live groups in an       O O # O . # # O O . #   2.5 intersections
  287. > infinite board. (These groups are  . # O # # . O # O # .       per group.
  288. > only alive in seki, of course.)    # . O O # O . # # O O
  289. >
  290. > This density is noticably better than any other solutions seen on the net.
  291.  
  292.      There is also a variation on this configuration that proves useful,
  293. namely:
  294.  
  295.   . # #
  296.   # . O #
  297.   O O . # #
  298.     O # . O #
  299.       O O . # #
  300.         O # . O #
  301.           O O . # #
  302.  
  303. Here we have shown only a single strip.  These strips can be put together to
  304. cover an infinite board.  This second configuration allows the boundary
  305. connectivity to change phase.  He also writes
  306.  
  307. > It's a bit tricky fitting in stuff round the edges of a finite board, though.
  308. > In view of the messy nature of my solution, and the alleged Dutch publication
  309. > of a 130-odd group formation, I'm far from sure this is best possible. It
  310. > must be close though.
  311. >
  312. > So here's my solution; 128 groups (counting orthogonal connections only)
  313. >                        114 groups (counting 2 bits joined by an eye as the same)
  314.  
  315.  
  316.      We were able to get to the 130-odd group level.  We found the following:
  317.  
  318.            A B C D E F G H J K L M N O P Q R S T
  319.           *-------------------------------------*
  320.        19 |. # . O # O O . O # O O . O O # # . #| 19
  321.        18 |O # O . # # O O . # # O O . # O # # .| 18
  322.        17 |O O # # . O # O # . O # O # . O # # #| 17
  323.        16 |. # O # O . # # O O . # # O O : O O #| 16
  324.        15 |# . O O # # . O # O # . O # # O . # O| 15
  325.        14 |O O . # O # O . # # O O . # # O # . O| 14
  326.        13 |# O # . O O # # . O # O # . O # O O .| 13
  327.        12 |# # O O . # O # O . # # O O . # # O O| 12
  328.        11 |. # # O # . O O # # . O # O # . O # O| 11
  329.        10 |# . O # O O . # O # O . # # O O . # #| 10
  330.         9 |# O . # # O # . O O # # . O # O # . O|  9
  331.         8 |O # # . O # O O . # O # O . # # O O .|  8
  332.         7 |O O # O . # O O # . O O # # . O # O O|  7
  333.         6 |. O O # # : # # O O . # O # O . # # O|  6
  334.         5 |O . # O O # . O # O # . O O # # . O #|  5
  335.         4 |# # . O O # O . # # O O . # O # O . #|  4
  336.         3 |O O O . # O # # . O # O # . O O # # .|  3
  337.         2 |O O O # . O O # O . # # O O . # O # O|  2
  338.         1 |O O O # O . O O # # . # # O # . O O :|  1
  339.           *-------------------------------------*
  340.            A B C D E F G H J K L M N O P Q R S T
  341.  
  342.      This arrangement has 132 groups (in the sense of connected components).
  343. If we allow connections though empty intersections, then the connected
  344. components combine to form 65 areas.  The three colons are empty intersections
  345. that behave as false eyes (as opposed to seki points).  The false eyes at F6
  346. and Q16 are the centers of "windmills".  These windmills are there to solve
  347. phase problems with the edges of the board.  Each one forms a single area
  348. with 4 connected components.  The false eye at T1 is the center of another
  349. windmill.  The following rearrangement of that corner makes this clear.
  350.  
  351.                         # # O O . # #| 10
  352.                         . O # O # . O|  9
  353.                         O . # # O O .|  8
  354.                         # # . O # O O|  7
  355.                         O # O . # O O|  6
  356.                         O O # # : # #|  5
  357.                         . # O O # . O|  4
  358.                         # . O O # O .|  3
  359.                         O O . # O # #|  2
  360.                         # O # . O O .|  1
  361.                         -------------*
  362.                         N O P Q R S T
  363.  
  364.      This rearrangement does not change the area or component counts.
  365.